#ifndef SPW_ALLOC_H_
#define SPW_ALLOC_H_
#include <memory/spw_new.h>
#include <utility/spw_move_in.h>
#include <exception/spw_stdexcept.h>
#include <iterator/spw_iterator.h>

/*
* 分配器提供给内部容器使用. 因为容器要存放数据[从堆上申请内存，如vector, list，map等，
* 需要栈上内存容器，如数组，不需要new], 必然要申请内存来存放这些数据
* 而用户没有自己使用new，delete去申请和释放堆上的内存，这一切都是分配器完成的
*/

// # 默认的内存分配器
// 使用new和delete
namespace spwstd {

template <typename T>
struct DefaultAlloc{
    using ValueType = T;
    using SizeType = spwconfig::size_t;
    using DifferType = spwconfig::ptrdiff_t;
    using Pointer = T*;

    // - 在无状态分配器，默认构造函数等，都为空
    DefaultAlloc() noexcept {}

    DefaultAlloc(const DefaultAlloc&) noexcept {}

    template<typename U>
    DefaultAlloc(const DefaultAlloc<U>&) noexcept {}

    ~DefaultAlloc() noexcept {}

    // - 分配内存函数
    ValueType* allocate (SizeType n, const void* = 0) {
        if(n > this->maxSize()) {
            throw  spwstd::spwexcept::BadAlloc();
        }
        return reinterpret_cast<ValueType*>(::operator new(n * sizeof(ValueType)));
    }

    void deallocate(ValueType* ptr, SizeType) {
        ::operator delete(ptr); 
    }

    SizeType maxSize() const noexcept{
        return SizeType(-1) / sizeof(ValueType);
    }

};

// - 在比较两个无状态分配器时，无条件为true
// 在比较两个非静态状态分配器时，要比较状态
template<typename T>
inline bool operator== (
    const DefaultAlloc<T>&,
    const DefaultAlloc<T>& )
{
    return true;
}

template<typename T>
inline bool operator!= (
    const DefaultAlloc<T>&,
    const DefaultAlloc<T>& )
{
    return false;
}

// # 内存池分配内存
// 内存池把一整块内存分配给freelists, 并把以相应申请内存大小串成链表，
// 分配的一整块内存，为什么把以数组形式，而是以链表
// 答：主要是在释放内存，链表很简单重新回收内存再次使用。
// 而数组分配一样，但释放后不象链表把释放内存重新链接在链表上，等待再次分配.
// 不用关心这个释放内存的具体位置。但数组必须知道具体位置才可以使用
// 
class PoolAllocBase {
public:
    using SizeType = spwconfig::size_t;
    using DifferType = spwconfig::ptrdiff_t;
protected:
    // 无名枚举，
    // 当需要只是一组整型常量，而不是用于声明变量类型
    // 这些整型常量，作用域仅限在该类中，且只有该类中会使用到
    // 这组枚举. 无名枚举只有在声明是定义
    enum { Align = 8 }; // 该分配器分配最小内存
    enum { MaxBytes = 128}; // 该分配器分配最大内存
    enum { NumFreeLists = static_cast<SizeType>(MaxBytes)
                          / static_cast<SizeType>(Align) }; // freelist个数,128/8=16

    union Obj {
        union Obj* freelist_link_; // 
        char client_data[1];
    };

    // volatile，数组内部Obj指针不允许编译器优化
    // 从8-128，提供16个不同大小的链表. 根据申请内存大小
    // 从相应链表中获取内存
    static Obj* volatile s_Freelists[NumFreeLists];

    // 池子分配状态
    static char* s_StartFree; // 池子起始位置
    static char* s_EndFree;   // 池子结束位置
    static SizeType s_HeapSize; // 已分配给freelists的内存大小

    // 大于该bytes最靠近的链表
    // +7, 但只保留8的倍数
    SizeType roundUp(SizeType bytes) {
        return ((bytes + static_cast<SizeType>(Align) - 1) 
               & ~(static_cast<SizeType>(Align) - 1));
    }
    // 获取相应数据大小链表的freelist指针, 指向可以获得内存位置
    // 返回一个指针，其指向一个不允许优化的指针且指向const Obj
    // (const Obj *volatile) *, 一个指针指向(const Obj *volatile)
    // (const Obj)* volatile, 这个指针不允许编译器优化，且指向const Obj
    Obj *volatile *getFreelist(SizeType) noexcept;

    // 建立一个相应内存的链表，分配一个内存然后返回地址
    void* refill(SizeType);

    // 分配一大块内存作为池子，分配给不同内存的链表
    // int& 默认20个相应大小内存的容量
    char* allocateChunk(SizeType, SizeType&);
};

template<typename T>
class PoolAlloc: private PoolAllocBase {
public:
    using ValueType = T;
    using Pointer = T*;

    // 同上，无状态分配器，构造函数等都为空
    PoolAlloc() noexcept {}
    PoolAlloc(const PoolAlloc&) noexcept {}

    template<typename U>
    PoolAlloc(const PoolAlloc<U>&) noexcept {}
    ~PoolAlloc() noexcept {}

    SizeType maxSize() const noexcept{
        return SizeType(-1) / sizeof(ValueType);
    }

    ValueType* allocate(SizeType n, const void* = 0);
    void deallocate(ValueType* p, SizeType n);
};

template<typename T>
typename PoolAlloc<T>::ValueType* 
PoolAlloc<T>::allocate(SizeType n, const void*) {
    Obj* result = nullptr;
    if(0 == n){
        return reinterpret_cast<ValueType*>(result);
    } else {
        if (n > this->maxSize()) {
            // 当分配内存大于最大值，直接抛出异常
            return spwstd::spwexcept::BadAlloc();
        } else {
            const SizeType bytes = n * sizeof(ValueType);
            if (bytes > static_cast<SizeType>(MaxBytes)) // 大于128
            {
                result = reinterpret_cast<ValueType*>(::operator new(bytes));
            } else { // 从链表中获取内存
                // 得到指向相应链表的指针
                Obj * volatile *freelist = getFreelist(bytes);
                result = *freelist;
                if(0 == result) {
                    // 没有找到可用的freelist, 即没有相应链表, 没开始分配或原链表分配完
                    // 造作一个相应内存的链表
                    result = reinterpret_cast<ValueType*>(refill(roundUp(bytes)));
                } else {
                    *freelist = result->freelist_link_;
                }
                if(result == 0)
                    throw spwstd::spwexcept::BadAlloc();
            }
            return result;
        }
    }
}

template<typename T>
void PoolAlloc<T>::deallocate(ValueType* p, SizeType n) {
    const SizeType bytes = n * sizeof(ValueType);
    if(bytes > static_cast<SizeType>(MaxBytes)) {
        ::operator delete(p);
    } else {
        Obj* volatile* freelist = getFreelist(bytes);
        Obj* q = reinterpret_cast<Obj*>(p);
        q->freelist_link_ = *freelist;
        *freelist = q;
    }
}

// 同上，在比较两个无状态分配器时，无条件为true
// 在比较两个非静态状态分配器时，要比较状态
template<typename T>
inline bool operator==(const PoolAlloc<T>&, const PoolAlloc<T>&)
{ return true; }

template<typename T>
inline bool operator!=(const PoolAlloc<T>&, const PoolAlloc<T>&)
{ return false; }

// TODO:# 分配固定大小内存分配器

// # allocater 对外的接口
template<typename T, typename Alloc = DefaultAlloc<T>>
class AllocInterface {
public:
    static T* s_allocate(spwconfig::size_t n) {
        return 0==n? 0 : reinterpret_cast<T*>( Alloc().allocate( n ));
    }
    static T* s_allocate() {
        return reinterpret_cast<T*>( Alloc().allocate( 1 ));
    }
    static void s_deallocate(T* p, spwconfig::size_t n) {
        if (0!=n)
            Alloc().deallocate(p, n*sizeof(T));
    }
    static void s_deallocate(T* p) {
        Alloc().deallocate(p, sizeof(T));
    }

    template<class... Args>
    static void s_construct(T* p, Args&&... args) {
        ::new (p) T(spwstd::spwuti::forward<Args>(args)...);  
    }

    template<class Iter, class... Args>
    static void s_construct(Iter p, Args&&... args) {
        ::new (&*p) typename spwstd::IteratorTraits<Iter>::ValueType(spwstd::spwuti::forward<Args>(args)...);  
    }

    static void s_destroy(T* ptr) {
        ptr->~T();
    }

    template<typename Iter>
    static void s_destroy(Iter ptr) {
        ptr->~T();
    }
};

/* allocator traits*/
template<typename AllocT>
struct AllocTraits {
    using ValueType = typename AllocT::ValueType;
    using Pointer = typename AllocT::Pointer;
    using DifferType = typename AllocT::DifferType;
    using SizeType = typename AllocT::SizeType;
};

// TODO:allocate_ptr, RAII, 管理allocator分配的动态内存 
//
} // namespace spwstd
#endif // SPW_ALLOC_H_
